In applications that create, store or transmit information, it may be desirable to designate certain bit patterns as "forbidden" such that these patterns do not occur in a stream of digital words conveying the information. One example is found in systems that use a "sync" pattern to mark the boundary of a frame or packet of information in a data stream. The sync pattern is used to align or synchronize equipment that is intended to process the frame or packet of information. In such cases, it can be useful to prevent the sync pattern from occurring in the data stream itself so that information within the data stream cannot be falsely identified as a sync pattern.
Another example arises in the field of digital audio transport. The serial transmission of digital audio information is the subject of various international standards such as AES3 (ANSI S4.40) published by the Audio Engineering Society (AES). This standard defines serial transmission of two-channel digital audio represented in a linear pulse code modulation (PCM) form. According to this standard, PCM samples for two channels are interleaved and conveyed in pairs. In the case of 16-bit PCM that is expressed in two's complement representation, these amplitude values can vary within a range from 32767 (expressed in hexadecimal notation as 0x7FFF) through -32768 (0x8000). In this representation, a slight amount of asymmetry is introduced by virtue of the most-negative value being one unit of magnitude larger than the most-positive value.
Some equipment is designed to prevent this asymmetry by avoiding the most-negative value of 0x8000. If this value is not used for conveying PCM amplitude, it can be and sometimes is used for some other purpose such as conveying control or signaling information. If a PCM sample having this value does occur in the audio information, it could be incorrectly identified as control or signaling information; therefore, this particular data pattern should be avoided in the audio information. This can be accomplished by replacing the forbidden value of -32768 (0x8000) with another value such as -32767 (0x8001). This substitution introduces an irreversible error in the audio information but, for PCM audio information, the error is insignificant.
A problem arises when the information is not PCM audio samples but is a digital bit stream that represents audio information in an encoded form. Two examples of such bit streams are those conforming to Dolby AC-3 and various ISO MPEG standards. In such cases, substituting one value such as 0x8001 for another value such as 0x8000 almost certainly represents an audible change in the audio information and, because this substitution cannot be reversed, will cause unacceptable distortion in the recovered audio information.
This problem is significant because there is a growing interest to use equipment originally designed for one- or two-channel PCM bit streams such as AES3-compatible bit streams to convey more audio channels in an encoded form such as the AC-3 and MPEG forms mentioned above. One the one hand, these encoded forms can include forbidden data patterns that are not conveyed correctly because the forbidden data patterns are incorrectly interpreted as control or signaling information. On the other hand, known substitution methods for avoiding these forbidden data patterns introduce irreversible changes in the encoded information that cause audible distortion in recovered audio.
This problem can be solved by preventing the occurrence of forbidden data patterns in the encoded audio information. One way to accomplish this is to put the encoded audio information in a form that ensures all forbidden data patterns are avoided. For example, the digital audio information can be parsed into a sequence of n-bit words and each word converted into longer m-bit codes that can be guaranteed to avoid specific forbidden data patterns. The m-bit codes can be conveyed without difficulty because they do not include any forbidden data patterns. The original encoded audio information can be recovered by converting each m-bit code into an appropriate n-bit word. Many suitable n-to-m bit coding schemes are known. The problem with this approach is that it requires an overhead of (m-n) bits per word. In many applications, this overhead imposes storage capacity requirements or channel bandwidth requirements that are difficult if not impossible to satisfy.
Another way to prevent the occurrence of forbidden data patterns in encoded audio information is to design the syntax of the encoded stream to avoid generating a forbidden data pattern. For example, the value 0x8000 could be avoided by ensuring the encoded stream never contains more than fourteen consecutive zero-bits because this forbidden data pattern consists of fifteen zero-bits following a single one-bit. The problem with this approach is that it imposes restrictions on the elementary bitstream syntax that must be considered at every stage of the encoding process. Furthermore, this approach may impose extremely complex restrictions on the syntax if more than one forbidden data pattern is to be avoided.